package main.leetcode.offer.firstround.from51to68;

/**
 * 69.二叉树的下一个节点
 *
 * <p>给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 *
 * <p>注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
 */
public class ex69 {
    public TreeLinkNode getNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        }

        // 存在右节点，向右子树的左下
        if (pNode.right != null) {
            TreeLinkNode pre = pNode.right;
            TreeLinkNode node = pre.left;
            while (node != null) {
                pre = node;
                node = node.left;
            }
            return pre;
        }

        // 不存在右节点，向上
        while (pNode.next != null) {
            if (pNode.next.left == pNode) {
                return pNode.next;
            }
            pNode = pNode.next;
        }

        return null;
    }
}

class TreeLinkNode {
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;
    private int val;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
